package com.example.demo;

import com.example.leetcode.common.ListNode;
import com.example.leetcode.common.ListNodeWrapper;

import java.util.Deque;
import java.util.LinkedList;


/**
 * @author zhanpengguo
 * @date 2020-11-01 12:15
 */
public class ListNodeDemo {

    /**
     * 翻转链表
     * @param head
     * @return
     */
    public ListNode reverse(ListNode head) {
        // 最后一个节点指向null
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 从尾到头打印链表
     * @param head
     */
    public void tailToHead(ListNode head) {
        Deque<ListNode> stack = new LinkedList<>();
        while (head != null) {
            // 压入栈中
            stack.push(head);
            head = head.next;
        }
        while (!stack.isEmpty()) {
            // 弹出
            ListNode node = stack.pop();
            System.out.println(node.val);
        }
    }

    /**
     * 合并两个有序链表 递归
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    /**
     * 合并两个有序链表 迭代
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

    /**
     * 倒数第k个元素
     * @param head
     * @param k
     * @return
     */
    public ListNode kthToLast(ListNode head, int k) {
        ListNode first = head;
        ListNode second = head;
        //第一个指针先走k步
        while (k-- > 0) {
            first = first.next;
        }
        //然后两个指针在同时前进
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        return second;
    }

    /**
     * 链表是否有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != slow) {
            if (fast == null || fast.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

    /**
     * 链表中环的入口节点
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        do {
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        } while (fast != slow);
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    public static void main(String[] args) {
        ListNode head = ListNodeWrapper.stringToListNode("[1,2,3]");
        ListNodeDemo demo = new ListNodeDemo();
//        ListNode node = demo.reverse(head);
//        ListNodeWrapper.prettyPrintLinkedList(node);

//        demo.tailToHead(head);

        ListNode l1 = ListNodeWrapper.stringToListNode("[1,3,5]");
        ListNode l2 = ListNodeWrapper.stringToListNode("[2,4,6]");
        ListNode node = demo.mergeTwoLists1(l1, l2);
        ListNodeWrapper.prettyPrintLinkedList(node);

//        int i = demo.kthToLast(head, 1);
//        System.out.println(i);
    }
}
